package org.algorithm.二师兄.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;

import java.util.*;

/**
 * @Date 2022/2/18
 * @Link {https://leetcode-cn.com/problems/aMhZSa/}
 */
public class 回文链表 {

    public static void main(String[] args) {
        ListNode listNode = ListNode.build(1,2,3,3,2,1);
        System.out.println("队列处理 = " + isPalindrome(listNode));
        System.out.println("栈处理 = " + isPalindrome1(listNode));
        System.out.println("数组处理 = " + isPalindrome2(listNode));
        System.out.println("快慢指针 + 反转链表 = " + isPalindrome3(listNode));
        System.out.println("快慢指针 + 栈 = " + isPalindrome4(listNode));
    }


    // 1. 常规思路
    public static boolean isPalindrome(ListNode head){
        if (head == null || head.next == null) return false;
        // 1.1 挨个碰一遍
        Queue<Integer> queue = new LinkedList<>();
        ListNode tem = head;
        while (tem != null) {
            queue.offer(tem.val);
            tem = tem.next;
        }

        // 不是偶数长度  不是回文
        if (queue.size() % 2 != 0) return false;

        // 1.2 再比较一遍，如果有一个不对， 就不对
        for (int i = 0; i < queue.size(); i++) {
            if (queue.poll() != head.val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // 2. 使用栈来做
    public static boolean isPalindrome1(ListNode head){
        if (head == null || head.next == null) return false;

        Stack<Integer> stack = new Stack<>();
        ListNode tem = head;
        while (tem != null) {
            stack.push(tem.val);
            tem = tem.next;
        }
        if (stack.size() % 2 != 0) return false;

        // 1.2 再比较一遍，如果有一个不对， 就不对
        for (int i = 0; i < stack.size() / 2; i++) {
            if (stack.pop() != head.val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // 3. 使用数组
    public static boolean isPalindrome2(ListNode head){
        if (head == null || head.next == null) return false;
        List<Integer> list = new ArrayList<>();
        ListNode tem = head;
        while (tem != null) {
            list.add(tem.val);
            tem = tem.next;
        }

        // 双指针加速判断
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 4. 反转链表判断
    public static boolean isPalindrome3(ListNode head){
        if (head == null || head.next == null) return false;
        // 快慢指针， 慢指针走到中间
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 设置虚拟节点
        ListNode dummy = slow;
        ListNode prev = null;
        // 反转链表
        while (dummy != null) {
            ListNode temp = dummy.next;
            dummy.next = prev;
            prev = dummy;
            dummy = temp;
        }

        while (prev != null) {
            if (prev.val != head.val) {
                return false;
            }
            prev = prev.next;
            head = head.next;
        }
        return true;
    }

    // 栈的升级版， 思路从 第三个方法 得到的。  快慢指针 + 栈
    public static boolean isPalindrome4(ListNode head){
        if (head == null || head.next == null) return false;
        // 快慢指针， 慢指针走到中间
        ListNode slow = head;
        ListNode fast = head;
        Stack<Integer> stack = new Stack<>();
        while (fast != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        while (stack.empty()) {
            if (stack.pop() != head.val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
}
